package com.cat.graphTheory;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/path-with-maximum-probability/description/
 * @create 2025/9/24 18:45
 * @since JDK17
 */

public class Solution29 {
    class Pair {
        int pos;
        double val;
        public Pair(int pos, double val) {
            this.pos = pos;
            this.val = val;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int s, int e) {
        List<Pair>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        double[] dis = new double[n];
        int m = edges.length;
        for (int i = 0; i < m; i++) {
            g[edges[i][0]].add(new Pair(edges[i][1], succProb[i]));
            g[edges[i][1]].add(new Pair(edges[i][0], succProb[i]));

        }
        PriorityQueue<Pair> heap = new PriorityQueue<>((a, b) -> Double.compare(a.val, b.val));
        Arrays.fill(dis, 0);
        heap.add(new Pair(s, 1));
        while (!heap.isEmpty()) {
            var p = heap.poll();
            if (p.val < dis[p.pos]) {
                continue;
            }
            for (var u : g[p.pos]) {
                if (p.val * u.val > dis[p.pos]) {
                    dis[p.pos] = p.val * u.val;
                    heap.add(new Pair(u.pos, dis[p.pos]));
                }
            }
        }

        return dis[e];
    }
}
